1105. 填充书架【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划

1. 📝 题目描述

• leetcode

给定一个数组 books，其中 books[i] = [thicknessi, heighti] 表示第 i 本书的厚度和高度。你也会得到一个整数 shelfWidth。

按顺序 将这些书摆放到总宽度为 shelfWidth 的书架上。

先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelfWidth ），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。

需要注意的是，在上述过程的每个步骤中，摆放书的顺序与给定图书数组 books 顺序相同。

• 例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。

每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。

以这种方式布置书架，返回书架整体可能的最小高度。

---

示例 1：

输入：books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4
输出：6
解释：
3 层书架的高度和为 1 + 3 + 2 = 6。
第 2 本书不必放在第一层书架上。

示例 2：

输入: books = [[1,3],[2,4],[3,2]], shelfWidth = 6
输出: 4

---

提示：

• 1 <= books.length <= 1000
• 1 <= thicknessi <= shelfWidth <= 1000
• 1 <= heighti <= 1000

2. 🎯 s.1 - 动态规划

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[][]} books
 * @param {number} shelfWidth
 * @return {number}
 */
var minHeightShelves = function (books, shelfWidth) {
  const n = books.length
  const dp = new Array(n + 1).fill(Infinity)
  dp[0] = 0
  for (let i = 1; i <= n; i++) {
    let width = 0,
      height = 0
    for (let j = i; j >= 1; j--) {
      width += books[j - 1][0]
      if (width > shelfWidth) break
      height = Math.max(height, books[j - 1][1])
      dp[i] = Math.min(dp[i], dp[j - 1] + height)
    }
  }
  return dp[n]
}

• 时间复杂度：$O(n\times m)$，其中 $n$ 是书的数量，$m$ 是每层能放的最大书数
• 空间复杂度：$O(n)$，dp 数组的开销

算法思路：

• dp[i] 表示前 i 本书的最小书架高度
• 对于第 i 本书，枚举它和前面若干本书放在同一层，只要总宽度不超过 shelfWidth
• 取这一层的最大高度加上前面层的最小高度，取所有方案的最小值